package 力扣.二分.三步切分法;

public class 搜索旋转排序数组33 {
    public int search(int[] nums, int target) {
         if(nums == null || nums.length == 0){
             return -1;
         }
         int N = nums.length;
         int l = 0,r = N;
         while (l < r){
             int m = (l +((r - l) >> 1));
             if (nums[l] == target){
                 return l;
             }
             if (nums[m] == target){
                 return m;
             }
             if (nums[r - 1] == target){//注意是 r-1 ！！！
                 return r-1;
             }
             //切分区间
             if (nums[m] > nums[l]){//m在左线段中
                 if (nums[l] < target && target < nums[m]){
                     r = m;//扔掉右半部分
                 }else{
                     l = m + 1;//扔掉左半部分
                 }
             }else {//m在右线段中
                 if (nums[m] < target && target < nums[r - 1]){//别忘记左闭右开
                     l = m + 1; //扔掉左半部分
                 }else {
                     r = m; //扔掉右半部分
                 }
             }
         }
         return -1;
    }
    public int search2(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return -1;
        }
        int l = 0 ,r = nums.length;
        while (l < r){
            int m = l + ((r - l) >> 1);
            if (nums[m] == target){
                return m;
            }
            if (nums[l] == target) {
                return l;
            }
            if (nums[r - 1] == target){
                return r - 1;
            }
            if (nums[m] > nums[l]){//m在左线段
                if (target > nums[l] && target < nums[m]){//扔掉m右边的所有元素
                    r = m;
                }else{//扔掉m左边的元素
                    l = m + 1;
                }
            }else {//m在右线段
                if (target > nums[m] && target < nums[r - 1]){//扔掉m左边的元素
                    l = m + 1;
                }else{//扔掉m右边的元素
                    r = m;
                }
            }
        }
        return -1;
    }
}
